import java.util.Scanner;

public class HexadecimaltoOctal2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String a[] = new String[n];
        for (int i = 0 ; i < n ; i++){
            a[i] = sc.next();
        }

        for (int i = 0 ; i < n ; i++){
            String Bain = toBinary(a[i]);
            int len_strBin = Bain.length();
            if(len_strBin%3==1) Bain = "00" + Bain;
            if(len_strBin%3==2) Bain = "0" + Bain;
            String Octal = toOctal(Bain);
            System.out.println(Octal);
        }
    }

    public static String toOctal(String str) {
        int len = str.length();
        StringBuffer a = new StringBuffer();
        int k;
        if(str.substring(0, 3).equals("000")) k=3;
        else k=0;
        for (int i = k ; i < len - 2 ; i+=3){
            String b = str.substring(i,i+3);
            if (b.equals("000")) a.append("0");
            else if(b.equals("001")) a.append("1");
            else if(b.equals("010")) a.append("2");
            else if(b.equals("011")) a.append("3");
            else if(b.equals("100")) a.append("4");
            else if(b.equals("101")) a.append("5");
            else if(b.equals("110")) a.append("6");
            else if(b.equals("111")) a.append("7");
        }
        return a.toString();
    }

    public static String toBinary(String str) {
        int len = str.length();
        StringBuffer a = new StringBuffer();
        for (int i = 0 ; i < len ; i++){
            switch (str.charAt(i)) {
                case '0': a.append("0000"); break;
                case '1': a.append("0001"); break;
                case '2': a.append("0010");break;
                case '3': a.append("0011"); break;
                case '4': a.append("0100"); break;
                case '5': a.append("0101"); break;
                case '6': a.append("0110"); break;
                case '7': a.append("0111"); break;
                case '8': a.append("1000"); break;
                case '9': a.append("1001"); break;
                case 'A': a.append("1010"); break;
                case 'B': a.append("1011"); break;
                case 'C': a.append("1100"); break;
                case 'D': a.append("1101"); break;
                case 'E': a.append("1110"); break;
                case 'F': a.append("1111"); break;
                default: break;
            }
        }
        return a.toString();
    }
}
